/*
	解法：移除单链表结点
	为什么：无
	时间复杂度：O(n)，空间复杂度：O(1)
 */

#include <iostream>
#include <vector>

using namespace std;

/**
 * 单链表结点
 */
struct ListNode
{
	int val;
	ListNode* next;
	ListNode() : val(0), next(nullptr) {}		//无参构造，用于默认构造
	ListNode(int x) : val(x), next(nullptr) {}	//有参构造，最常用。（函数重载，构造函数可以多个，参数类型不同即可）
	ListNode(int x, ListNode* next) : val(x), next(next) {}		//有参构造，常用于一次性接上后继节点
};

class Solution
{
public:
	ListNode* removeElements(ListNode* head, int val)
	{
		ListNode* dummy = new ListNode(-1);
		dummy->next = head;
		
		ListNode* prev = dummy;		//prev：curr 的前一个节点（previous node），用于重新连接链表
		ListNode* curr = head;		//curr：当前正在检查的节点（current node），用来判断是否要删除
		
		while (curr != nullptr)
		{
			if (curr->val == val)
			{
				prev->next = curr->next;
				delete curr;
				curr = prev->next;
			}
			else
			{
				prev = curr;
				curr = curr->next;
			}
		}
		
		ListNode* newHead = dummy->next;		//ListNode* newHead = head 错，head 可能在删除节点过程中已经被删掉或改变了
		delete dummy;
		return newHead;
	}
};

// 辅助函数：根据 vector 构建链表
ListNode* buildList(const vector<int>& nums)
{
	ListNode* dummy = new ListNode(-1);
	ListNode* tail = dummy;
	
	for (int i = 0; i < (int)nums.size(); ++i)
	{
		tail->next = new ListNode(nums[i]);
		tail = tail->next;
	}
	
	ListNode* head = dummy->next;
	delete dummy;
	return head;
}

// 辅助函数：打印链表
void printList(ListNode* head)
{
	while (head != nullptr)
	{
		cout << head->val;
		if (head->next != nullptr)
		{
			cout << " -> ";
		}
		head = head->next;
	}
	cout << endl;
}

// 辅助函数：释放链表内存
void deleteList(ListNode* head)
{
	while (head != nullptr)
	{
		ListNode* temp = head;
		head = head->next;
		delete temp;
	}
}

int main()
{
	vector<int> input = {6, 2, 3};
	int val = 6;
	
	ListNode* head = buildList(input);
	
	cout << "原始链表: ";
	printList(head);
	
	Solution sol;
	ListNode* result = sol.removeElements(head, val);
	
	cout << "删除 " << val << " 后的链表: ";
	printList(result);
	
	deleteList(result);
	
	return 0;
}

